<HTML>
<BODY>
<PRE>
<!-- Manpage converted by man2html 3.0.1 -->


<B><A HREF="BTREE.html">BTREE(3)</A></B>						 <B><A HREF="BTREE.html">BTREE(3)</A></B>


</PRE>
<H2>NAME</H2><PRE>
       btree - btree database access method


</PRE>
<H2>SYNOPSIS</H2><PRE>
       <B>#include</B> <B>&lt;sys/types.h&gt;</B>
       <B>#include</B> <B>&lt;db.h&gt;</B>


</PRE>
<H2>DESCRIPTION</H2><PRE>
       The  routine  <I>dbopen</I>  is the library interface to database
       files.  One of the supported file formats is btree  files.
       The  general description of the database access methods is
       in <B><A HREF="dbopen.html">dbopen(3)</A></B>, this manual page describes  only  the  btree
       specific information.

       The btree data structure is a sorted, balanced tree struc-
       ture storing associated key/data pairs.

       The btree access method specific data  structure  provided
       to  <I>dbopen</I>  is  defined in the &lt;db.h&gt; include file as fol-
       lows:

       typedef struct {
	      u_long flags;
	      u_int cachesize;
	      int maxkeypage;
	      int minkeypage;
	      u_int psize;
	      int (*compare)(const DBT *key1, const DBT *key2);
	      size_t (*prefix)(const DBT *key1, const DBT *key2);
	      int lorder;
       } BTREEINFO;

       The elements of this structure are as follows:

       flags  The  flag  value	is specified by <I>or</I>'ing any of the
	      following values:

	      R_DUP  Permit duplicate keys in the tree, i.e. per-
		     mit  insertion  if  the  key  to be inserted
		     already exists in	the  tree.   The  default
		     behavior,	as  described in <B><A HREF="dbopen.html">dbopen(3)</A></B>, is to
		     overwrite a matching key  when  inserting	a
		     new key or to fail if the R_NOOVERWRITE flag
		     is specified.  The R_DUP flag is  overridden
		     by   the  R_NOOVERWRITE  flag,  and  if  the
		     R_NOOVERWRITE flag is specified, attempts to
		     insert  duplicate	keys  into  the tree will
		     fail.

		     If the database contains duplicate keys, the
		     order  of	retrieval  of  key/data  pairs is
		     undefined if the <I>get</I> routine is  used,  how-
		     ever,  <I>seq</I>  routine  calls with the R_CURSOR
		     flag set  will  always  return  the  logical

			 August 18, 1994			1

<B><A HREF="BTREE.html">BTREE(3)</A></B>						 <B><A HREF="BTREE.html">BTREE(3)</A></B>

		     ``first'' of any group of duplicate keys.

       cachesize
	      A  suggested  maximum size (in bytes) of the memory
	      cache.  This value is <B>only</B> advisory, and the access
	      method  will allocate more memory rather than fail.
	      Since every search examines the root  page  of  the
	      tree, caching the most recently used pages substan-
	      tially improves access time.  In addition, physical
	      writes are delayed as long as possible, so a moder-
	      ate cache can reduce the number of  I/O  operations
	      significantly.   Obviously, using a cache increases
	      (but only increases) the likelihood  of  corruption
	      or  lost data if the system crashes while a tree is
	      being modified.  If <I>cachesize</I>  is  0  (no  size  is
	      specified) a default cache is used.

       maxkeypage
	      The  maximum number of keys which will be stored on
	      any single page.	Not currently implemented.

       minkeypage
	      The minimum number of keys which will be stored  on
	      any  single  page.  This value is used to determine
	      which keys will be stored on overflow  pages,  i.e.
	      if  a  key or data item is longer than the pagesize
	      divided by the minkeypage value, it will be  stored
	      on  overflow  pages  instead of in the page itself.
	      If <I>minkeypage</I> is 0 (no minimum number  of  keys  is
	      specified) a value of 2 is used.

       psize  Page  size is the size (in bytes) of the pages used
	      for nodes in the tree.  The minimum  page  size  is
	      512  bytes  and  the  maximum page size is 64K.  If
	      <I>psize</I> is 0 (no page size is specified) a page  size
	      is  chosen  based on the underlying file system I/O
	      block size.

       compare
	      Compare is the key comparison  function.	 It  must
	      return  an  integer less than, equal to, or greater
	      than zero if the first key argument  is  considered
	      to  be respectively less than, equal to, or greater
	      than the second key argument.  The same  comparison
	      function must be used on a given tree every time it
	      is opened.  If <I>compare</I> is NULL (no comparison func-
	      tion  is	specified),  the  keys are compared lexi-
	      cally,  with  shorter  keys  considered  less  than
	      longer keys.

       prefix Prefix is the prefix comparison function.  If spec-
	      ified, this routine must return the number of bytes
	      of  the  second key argument which are necessary to
	      determine that it is greater  than  the  first  key

			 August 18, 1994			2

<B><A HREF="BTREE.html">BTREE(3)</A></B>						 <B><A HREF="BTREE.html">BTREE(3)</A></B>

	      argument.   If  the  keys are equal, the key length
	      should be returned.  Note, the usefulness  of  this
	      routine  is  very data dependent, but, in some data
	      sets can produce significantly reduced  tree  sizes
	      and  search  times.   If	<I>prefix</I> is NULL (no prefix
	      function is specified), <B>and</B> no comparison  function
	      is  specified, a default lexical comparison routine
	      is used.	If <I>prefix</I> is NULL and a  comparison  rou-
	      tine is specified, no prefix comparison is done.

       lorder The  byte order for integers in the stored database
	      metadata.  The number should represent the order as
	      an  integer; for example, big endian order would be
	      the number 4,321.  If <I>lorder</I>  is	0  (no	order  is
	      specified) the current host order is used.

       If  the	file  already exists (and the O_TRUNC flag is not
       specified), the values specified for the parameters flags,
       lorder  and  psize are ignored in favor of the values used
       when the tree was created.

       Forward sequential scans of a tree are from the least  key
       to the greatest.

       Space freed up by deleting key/data pairs from the tree is
       never reclaimed, although it is	normally  made	available
       for reuse.  This means that the btree storage structure is
       grow-only.  The only  solutions	are  to  avoid	excessive
       deletions,  or  to create a fresh tree periodically from a
       scan of an existing one.

       Searches, insertions, and deletions in a  btree	will  all
       complete  in  O	lg  base N where base is the average fill
       factor.	Often, inserting ordered data into btrees results
       in  a low fill factor.  This implementation has been modi-
       fied to make ordered insertion the best case, resulting in
       a much better than normal page fill factor.


</PRE>
<H2>ERRORS</H2><PRE>
       The  <I>btree</I>  access  method routines may fail and set <I>errno</I>
       for any of the errors specified for  the  library  routine
       <B><A HREF="dbopen.html">dbopen(3)</A></B>.


</PRE>
<H2>SEE ALSO</H2><PRE>
       <B><A HREF="dbopen.html">dbopen(3)</A></B>, <B><A HREF="hash.html">hash(3)</A></B>, <B><A HREF="mpool.html">mpool(3)</A></B>, <B><A HREF="recno.html">recno(3)</A></B>

       <I>The</I>  <I>Ubiquitous</I>	<I>B-tree</I>,  Douglas Comer, ACM Comput. Surv.
       11, 2 (June 1979), 121-138.

       <I>Prefix</I> <I>B-trees</I>, Bayer and Unterauer, ACM  Transactions  on
       Database Systems, Vol. 2, 1 (March 1977), 11-26.

       <I>The</I>  <I>Art</I>  <I>of</I>  <I>Computer</I>  <I>Programming</I>  <I>Vol.</I>  <I>3:</I>  <I>Sorting</I> <I>and</I>
       <I>Searching</I>, D.E. Knuth, 1968, pp 471-480.

			 August 18, 1994			3

<B><A HREF="BTREE.html">BTREE(3)</A></B>						 <B><A HREF="BTREE.html">BTREE(3)</A></B>


</PRE>
<H2>BUGS</H2><PRE>
       Only big and little endian byte order is supported.

			 August 18, 1994			4

</PRE>
<HR>
<ADDRESS>
Man(1) output converted with
<a href="http://www.oac.uci.edu/indiv/ehood/man2html.html">man2html</a>
</ADDRESS>
</BODY>
</HTML>
